class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        powers = [0 for _ in range(15)]
        for i in range(len(powers)):
            powers[i] = 3**i

        def func(n, i):
            if n == 0:
                return True
            if n < 0:
                return False
            for j in range(i, len(powers)):
                if func(n - powers[j], j + 1):
                    return True

            return False

        return func(n, 0)
